站在正则表达式背后的……

作者：立体的萌

出品：程序员架构（ID：chengxuyuanjg）原创，转载请联系jb_quaner。

引子

当今社会是什么社会？信息社会！

信息社会最重要的东西（或者是最重要的之一）是什么？数据！

那数据又是以什么形式保存的？文本！！！

所以，对文本的操作（无非就是检索）就尤其重要，java中有个专门处理文本的类（中间数据类型）叫做String，String中提供了各类函数来帮助我们，不过，有个比String更加强大的工具：正则表达式；

你可能已经在猜测下面我要说的，什么元字符啦，各种主流语言中的正则表达式的使用啦，字符串验证、数字验证、混合验证啦……，说到这里，可能要让你们失望了，我不写这些东西；

正则表达式不就是用来做各种验证、匹配的吗？不写这些写啥呀？

我想说，这些东西当然很重要，不过，正则表达式并不是只有这些，比起掌握一个个命令更重要的是背后的原理，就如同编程！=敲代码一样，比起会写代码更重要的是编程思想，展示一个个的小兵不是我的菜（而且网上有很多资料，找到他们并不难），我要呈现的是正则表达式的匹配原理！

我们为什么如此的需要正则表达式？

乍一看，文本处理好像也不是很难，无非就是把需要的字符找出来，或者是两个字符进行比对，一点都不高深，不过，很多事情就怕多，怕杂，怕繁，再简单的东西，一旦多了也是个问题，或许你只是想找cat，结果你可能会把所有带有cat的单词都找出来了，结果还得重新找，如果只是10还好，给你找出100个这样的单词估计你得疯掉！总之，正则表达式用得好，可以拯救你的头发;

你总得明白正则表达式为何这么强大——匹配原理

起源有点意思

正则表达式有点像是深度学习——受神经科学的启发，正则表达式源于人类神经系统的早期研究，有两位科学家研究出了一套使用数学方式来描述神经网络的方式，并在1956年发表论文的时候明确提出了正则表达式的概念，“正则表达式是正则集的代数的表达式，”，真是太高大上了，让我这个生物盲情何以堪，反正明白正则表达式是生物学家受人类神经系统的启发而创造出来的然后被广泛应用于计算机的工具就好；

令人眼花缭乱的定义

正则表达式的定义简直比有机物的定义还繁杂：

一种用某种模式去匹配一类字符串的公式……

用来检查字符串中是否含有某种子串，将匹配的子串做替换或从某个字符串中取出符合某个条件的子串……

由普通字符和特殊字符组成的文字模式……

记录文本规则的代码……

用一个“字符串”来描述一个特征，然后去验证另一个“字符串”是否符合这个特征……

这些定义，似乎每个都对，又好像都不怎么完整，就像是霍华德的父亲的信件，他的朋友们各自编一个版本只有一个真版本混在其中，哪个是真是他自己来猜，这些个定义仿佛每个都是真的，又好像每个都是定义的一部分，或许你也很想像霍华德那样来一句：”我希望这些都是真的“

私以为，正则表达式的定义没那么复杂，就一句：处理文本的工具，完事儿，简洁明了，言简意赅；

有穷自动机（有穷状态自动机）

有穷自动机的意思是：**具备有限个状态，可以根据不同的条件在不同的状态之间转移；

我们生活当中就有有穷自动机，无人售货机就是的（或许不完全符合实际情况，不过原理明白就行），售货机中的商品都是整数（生活当中不是的，假设如此），并且只接受5元人民币这一种币值的货币，那么，根据余额的不同分为0元到5元这六种情况，假如你往里面放了5元，并点了一瓶3元的饮料，此时，状态就是：2元，退还给你2元之后状态切换到0元，那么， 从2元到0元就是状态转移，这个0元也叫最终状态，这一轮的状态转移结束之后，如果你再放进5元来买东西就是新一轮的状态转换了；

有穷自动机必须满足一下4个条件：     

1. 必须是有限个状态；
2. 具备状态转移的能力，也就是必须有状态转移函数；
3. 有且仅有一个开始状态；
4. 有一个或者是多个最终状态；

正则表达式使用的理论模型就是有穷自动机，具体的实现就是正则引擎，用正则表达式来处理字符串，必须首先生成自动机（这也是很多语言在使用正则表达式之前都是先编译一下正则对象的原因！）然后，无论输入什么字符，正则引擎都会在不同的状态之间游走；假如说有这么个表达式：a(bb)+a，它对应的自动机就是这样的：这里的S0-S4就是不同的状态，S0为开始状态，S4为最终状态，当前状态是S0的情况下，输入字符a，就会跳转到S1，如果不是a，则会直接退出；
有可能，同一个正则表达式对应的有穷自动机不止一台，也有可能是这样：还可以是这样：
这种情况是怎么样的呢？在状态S3，即便一个字符都没有输入，也不会停留下来，而是直接从哪来来的回哪里去了，也就是说，在某个时刻，自动机到底是在状态S1还是在状态S3是不确定的，但是这种 不确定性并不会影响自动机对于a(bb)+a的匹配，这三种情况的自动机都是等价的；
《编译原理》中提到过这样的概念：确定有限自动机(DFA)和不确定有限自动机（NFA），两者最大的区别在于他们的转换状态函数，后者可以对同一个字符串产生多种理解方式，而前者，只有一种理解方式，正则表达式就是后者；上面三张图，第一种就是DFA，后两种就是NFA；刚才又提到过DFA和NFA可以划等号，经过比较可以发现NFA构造起来会更加直观，也就是说构造NFA的难度小于DFA，因为DFA在任意时刻必须处于某个特定的状态，而NFA则可以处于多个状态中的某一个，使用NFA必须保存所有的可能的状态，并且在状态不可行时要回退到之前的状态，这就是回溯

回溯

这里要说明一下，回溯只属于NFA引擎，NFA匹配的时候，正则引擎并不知道当前的状态，只是在所有的状态不确定的地方把各个状态都保存下来，然后挨个尝试，如果发现走不通就原路返回，然后选择最近保存的其他的状态继续尝试，……，直到达到最终状态，这是成功的情况，不成功就是所有的状态都尝试过了依然没有找到最终状态；

总结

正则表达式可以做很多事情：查找重复的单词、检查Ｗｅｂ表单的输入、转换日期格式、检查拼写错误、为URL添加链接等等，可是什么让正则表达式这么强大呢?我们在学习一项技术的不仅要知其然，更要知其所以然！

关于作者

笔名立体的萌，是个工作还不到一年就辞职考研的的菜鸟，上学学习的是java,但是工作用的是C#,C#用途远远没有java范围广，再加上java是我的母语，所以很像回归java,不仅仅是提升技术能力，也有往大数据等高端领域发展的想法。

请作者吃糖

本文作者：立体的萌 

个人网址：https://blog.csdn.net/weixin_46107282

声明：本文为 程序员架构 原创投稿，未经允许请勿转载。

👇更多内容请点击👇